package com.hackerrank.challenges.helpmike;

import java.util.Scanner;

public class Solution {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int T = in.nextInt();
		for(int t = 0; t < T; t++) {
			long N = in.nextInt(), K = in.nextInt(), D = N / K, M = N % K, W = 0;
			// choose multiples of K
			W += D * (D - 1) / 2;
			if(M >= K / 2)
				W += (M - K / 2) * (D + 1) * (D + 1);
			else if(M <= (K - 1) / 2)
				W += ((K - 1) / 2 - M) * D * D;
			// choose multiples of K / 2
			if(K % 2 == 0) {
				if(M >= K / 2)
					W += (D + 1) * D / 2;
				else
					W += D * (D - 1) / 2;
			}
			if(M <= (K - 1) / 2)
				W += D * (D + 1) * M;
			else if(M >= K / 2)
				W += D * (D + 1) * (K - M - 1);
			System.out.println(W);
		}
	}
}
